Computer systems comprise input devices, output devices, one or more central processing units (CPUs), and storage capacity. The storage capacity takes form in many data storage devices, such as semiconductor memory, disc drives, and optical drives. An operating system provides an application environment and a file system that allocates or de-allocates storage capacity as files are created, modified, or deleted. Data storage systems such as servers also employ a file system for allocating storage capacity that is accessed through a network or other connection. Servers and storage arrays support data storage formats such as a redundant array of independent drives (RAID) that distributes stored information across a plurality of data storage devices. Data structures containing information describing the manner in which the data are mapped to memory is termed metadata. As files are created, modified, or deleted, metadata is updated to reflect the allocation or de-allocation (sometimes referred to collectively as “allocation”) of storage capacity.
The structure of metadata can significantly impact storage system performance. As the storage capacity of a system grows, the amount of metadata employed to manage the system also grows. As data structures using metadata become larger, the amount of time needed to parse information from the structures and to update these structures becomes significant.